import java.util.*;

public class test {
    // leetcode 3.无重复字符的最长子串
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int l = 0;
            int r = 0;
            int len = s.length();
            if (len <= 1) {
                return len;
            }
            int max = 0;
            //用于记录当前子串中出现过的字符
            HashSet<Character> set = new HashSet<>();
            //0~25代表26个字母
            int[] index = new int[200];
            for (; r < len && l < len; ) {
                //如果当前哈希表中没有该字符
                //dvabcvf
                while (r < len && !set.contains(s.charAt(r))) {
                    set.add(s.charAt(r));
                    //记录字符的下标
                    index[s.charAt(r)] = r;
                    r++;
                }
                if (r < len) {
                    //跳出循环,代表此时出现了重复字符,l = 该字符第一次出现的位置的下一个位置
                    l = index[s.charAt(r)] + 1;
                    r = l;
                    //判断是否更大
                    max = Math.max(max, set.size());
                    set.clear();
                } else {
                    return Math.max(max, set.size());
                }
            }
            return max;
        }
    }

    // leetcode 连续数组
    public int findMaxLength(int[] nums) {
        int sum = 0;
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        //初始化(如:[0,1] -> max应该等于[i - get(0)] 所以初始化的index应为-1)
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            //为1则++,为0则--,转化为求最长的和为0的子数组
            if (nums[i] == 1) {
                sum++;
            } else {
                sum--;
            }
            if (map.containsKey(sum)) {
                max = Math.max(max, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return max;
    }

    // leetcode 找到字符串中所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new LinkedList<>();
        int[] window = new int[26];
        for (char ch : p.toCharArray()) {
            window[ch - 'a']--;
        }
        int diffNum = p.length();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (window[ch - 'a'] >= 0) {
                diffNum++;
            } else {
                diffNum--;
            }
            window[ch - 'a']++;
            if (i >= p.length()) {
                char preCh = s.charAt(i - p.length());
                if (window[preCh - 'a'] <= 0) {
                    diffNum++;
                } else {
                    diffNum--;
                }
                window[preCh - 'a']--;
            }
            if (diffNum == 0) {
                result.add(i - p.length() + 1);
            }
        }
        return result;
    }
}
